package game.player.pacman;

import java.awt.Color;
import java.util.ArrayList;

import game.controllers.PacManController;
import game.core.G;
import game.core.Game;
import game.core.GameView;
import gui.AbstractPlayer;

/*
 * This is the class you need to modify for your entry. In particular, you need to
 * fill in the getAction() method. Any additional classes you write should either
 * be placed in this package or sub-packages (e.g., game.entries.pacman.mypackage).
 */
public class PacRob extends AbstractPlayer
{
	Game 	game;
	int[]	pacman;	//Distance of pacman from each node - updated each game tick
	int[]	closest; //Which ghost is nearest to each node
	int[][]	ghosts; //Distance of each ghost from each node - updated each game tick
	float[][] odds; //The odds for each ghost to reach each node
	float[] block; //The combined odds for any ghost to block each node
	int[]	bestPath; //The shortest route to the highest scoring node	

	private static final boolean PATH_DEBUG = true;
	private static final boolean ZONE_DEBUG = true;
	private static final float	CONTRAST = 0.75f;
	
	private static final int	CUTOFF = 350;
	private static final int	ESCAPE_PRIORITY = 50;
	private static final int	EDIBLE_PRIORITY = 125;
	private static final int	POWER_PRIORITY = 40;
	
	//Place your game logic here to play the game as Ms Pac-Man
	public int getAction(Game game,long timeDue)
	{
		this.game = game;
		float [] scores = scoreNodes();
		int best = bestNode(scores);
		int dir = bestDir(best, scores);
		
		if (PATH_DEBUG && dir != -1)
			for (int i=0; i<bestPath.length; i++)
				GameView.addPoints(game, new Color(1-block[bestPath[i]]*CONTRAST, 0, 0), bestPath[i]);
		
		return dir;
	}
	
	/*
	 * Returns the score for each node
	 * -1 means unsafe, anything positive means safe, the higher the score the better
	 */
	private float[] scoreNodes() {
		pacman = new int[game.getNumberOfNodes()];
		walk(game.getCurPacManLoc(), 0, -1);
		pacman[game.getCurPacManLoc()] = 0;
		ghosts = new int[Game.NUM_GHOSTS][game.getNumberOfNodes()];
		closest = new int[game.getNumberOfNodes()];
		odds = new float[Game.NUM_GHOSTS][game.getNumberOfNodes()];
		block = new float[game.getNumberOfNodes()];
		for (int g=0; g<Game.NUM_GHOSTS; g++) {
			if (game.getLairTime(g) > 0)
				ghostWalk(g, game.getInitialGhostsPosition(), game.getReverse(Game.INITIAL_GHOST_DIRS[g]), game.getLairTime(g), 1f);
			else
				ghostWalk(g, game.getCurGhostLoc(g), game.getReverse(game.getCurGhostDir(g)), 0, 1f);
		}
		
		float[] scores = new float[game.getNumberOfNodes()];
		for (int node=0; node<scores.length; node++) {
			scores[node] = -1;
			float chance = 1f;
			for (int g=0; g<Game.NUM_GHOSTS; g++)
				chance *= (1f-odds[g][node]);
			block[node] = 1f - chance;
			if (game.getNumNeighbours(node) > 0) {
				int nearest = -1;
			
				//Find nearest Hunting Ghost
				for (int g=0; g<Game.NUM_GHOSTS; g++) {
					int time = ghosts[g][node];
					if (time > game.getEdibleTime(g) && (nearest == -1 || time < ghosts[nearest][node]))
						nearest = g;
				}
				closest[node] = nearest;
				if ((node == game.getCurPacManLoc() || pacman[node] > 0) && (nearest == -1 || ghosts[nearest][node] - pacman[node] > Game.EAT_DISTANCE)) //Safe
					scores[node] = 1;
			}
		}				
		
		//Walk from the pacman position and remove any "safe" nodes that we can only reach via unsafe nodes
		boolean[] reachable = new boolean[game.getNumberOfNodes()];
		mark(game.getCurPacManLoc(), scores, reachable);
		//Remove unreachable nodes
		for (int node = 0; node < scores.length; node++)
			if (!reachable[node])
				scores[node] = -1;
			else if (ZONE_DEBUG)
				GameView.addPoints(game, new Color(0, 1-block[node]*CONTRAST, 0), node);
		
		//Score escape routes - these are the safe junction nodes closest to the event horizon
		int []eventHorizon = getEventHorizon(scores);
		int escapeRoutes = eventHorizon.length - Game.NUM_GHOSTS;
		if (escapeRoutes < 0)
			escapeRoutes = 0;

		for (int n: eventHorizon) {
			int jn = nearestJunction(n, scores);
			if (jn != -1) {
				float priority = ESCAPE_PRIORITY;
				if (closest[jn] != -1)
					priority += ghosts[closest[jn]][jn];
				scores[jn] += priority*(1-block[jn])/(escapeRoutes + 1);
			}
		}
		
		//Score Pills
		for (int p: game.getPillIndicesActive())
			if (reachable[p]) scores[p] += Game.PILL;
		
		//Score Power pill
		for (int p: game.getPowerPillIndicesActive()) {
			if (reachable[p]) {
				int mult = powerMultiplier(p);
				//The score for the power pill is not set if we are within 4 pixels but the ghosts aren't
				//This ensures we wobble near by until they get really close
				if (mult > 4 || (pacman[p] > 4 || (closest[p] != -1  && ghosts[closest[p]][p] <= 5 + Game.EAT_DISTANCE)))
					scores[p] += (float)POWER_PRIORITY * mult / (escapeRoutes + 1) + 1;
				else
					scores[p] = -1;
			}
		}
		
		//Score edible ghosts
		for (int g=0; g<Game.NUM_GHOSTS; g++) {
			int target = game.getCurGhostLoc(g);
			if (reachable[target] && game.isEdible(g)) {
				int dist = 2*pacman[target]; //Chasing takes twice the current distance;
				int jn = nextJunction(g); //Find junction that ghost is heading towards
				if (jn != -1) {
					if (reachable[jn]) {
						if (pacman[jn] >= ghosts[g][jn]) //Head to jn and then chase
							dist = ghosts[g][jn] + 2*pacman[jn];
						else //Head to jn then intercept
							dist = (ghosts[g][jn] + 2*pacman[jn])/3;
						
						if (dist < 2*pacman[target]) //Is is quicker to chase it down or intercept
							target = jn;
						else
							dist = 2*pacman[target];	
					}				
				} else //PacMan must be blocking the junction - simply head towards it
					dist = 2*pacman[target]/3;

				if (dist - game.getEdibleTime(g) < Game.EAT_DISTANCE) {
					scores[target] += EDIBLE_PRIORITY*(1-block[target])+10f/pacman[target];
				}
			}
		}
		
		return scores;
	}
	
	/*
	 * Find the next junction a ghost will reach.
	 * If we come across the pacman then return -1
	 */
	private int nextJunction(int g) {
		int node = game.getCurGhostLoc(g);
		int dir = game.getCurGhostDir(g);
		
		while (!game.isJunction(node)) {
			if (game.getCurPacManLoc() == node)
				return -1;
			int d = 0;
			while (game.getNeighbour(node, d) == -1 || d == game.getReverse(dir))
				d++;
			dir = d;
			node = game.getNeighbour(node, d);
		}
		
		if (game.getCurPacManLoc() == node)
			return -1;
		return node;
	}
	
	/*
	 * Find the nodes that are safe and have an unsafe neighbour
	 */
	private int [] getEventHorizon(float []scores) {
		ArrayList<Integer> edge = new ArrayList<Integer>();
		
		for (int n=0; n<game.getNumberOfNodes(); n++) {
			if (scores[n] >= 0) {
				boolean unsafe = false;
				for (int d=0; d<4; d++) {
					int next = game.getNeighbour(n, d);
					if (next != -1 && scores[next] < 0)
						unsafe = true;
				}
				if (unsafe)
					edge.add(n);
			}
		}
		int [] result = new int[edge.size()];
		for (int i=0; i<edge.size(); i++)
			result[i] = edge.get(i);
		return result;
	}
	
	/*
	 * Find the nearest junction to this node in the safe zone
	 */
	private int nearestJunction(int node, float[] scores) {	
		int prev = -1;
		while (!game.isJunction(node)) {
			int d = 0;
			while (game.getNeighbour(node, d) == -1 || game.getNeighbour(node, d) == prev || scores[game.getNeighbour(node, d)] == -1) {
				d++;
				if (d == 4)
					return -1;
			}
			prev = node;
			node = game.getNeighbour(node, d);
		}
		return node;
	}
	
	private void mark(int node, float[] scores, boolean[] reachable) {
		reachable[node] = true;
		for (int d=0; d<4; d++) {
			int next = game.getNeighbour(node, d);
			if (next != -1 && !reachable[next] && scores[next] >= 0)
				mark(next, scores, reachable);
		}
	}
	
	/*
	 * Returns how important the power pill is based on
	 * - number of hunter ghosts within eating distance of the power pill node
	 * - time to end of level
	 */
	private int powerMultiplier(int node) {
		int count = 0;
		int edibleTime = (int)(G.EDIBLE_TIME*(Math.pow(G.EDIBLE_TIME_REDUCTION,game.getCurLevel())));
		
		for (int g=0; g<Game.NUM_GHOSTS; g++)
			if (!game.isEdible(g) && game.getLairTime(g) <= 0 && ghosts[g][node] * 2 < edibleTime)
				count++;

		if (Game.LEVEL_LIMIT-game.getLevelTime() <= game.getNumActivePowerPills()*edibleTime+pacman[node])
			count += 3*game.getNumActivePowerPills();
		return count;
	}
	
	/*
	 * Walk the maze and record the distance to get to each node
	 * Hunting ghosts block the path
	 */
	private void walk(int node, int dist, int dir) {
		if (dist < CUTOFF && (pacman[node] == 0 || dist < pacman[node])) {
			pacman[node] = dist;
			if (!isBlocked(node, dist, dir))
				for (int d=0; d<4; d++) {
					int next = game.getNeighbour(node, d);
					if (next != -1)
						walk(next, dist+1, d);
				}
		}
	}
	
	/*
	 * Walk the maze as a ghost and record the distance to each node and the odds of blocking it
	 */
	private void ghostWalk(int g, int node, int banned, int dist, float chance) {
		if (dist < CUTOFF && (ghosts[g][node] == 0 || dist < ghosts[g][node])) {
			ghosts[g][node] = dist;			
			if (dist < game.getEdibleTime(g))
				dist++;
			else
				odds[g][node] = chance;
			chance /= (game.getNumNeighbours(node) - 1);
			for (int d=0; d<4; d++) {
				int next = game.getNeighbour(node, d);
				if (next != -1 && d != banned)
					ghostWalk(g, next, game.getReverse(d), dist+1, chance);
			}
		}
	}
	
	/*
	 * Power pills and hunter ghosts block the maze walk
	 */
	private boolean isBlocked(int node, int dist, int dir) {
		int p = game.getPowerPillIndex(node);
		if (p != -1 && game.checkPowerPill(p))
			return true;
		for (int g=0; g<Game.NUM_GHOSTS; g++)
			if (game.getEdibleTime(g) < dist && game.getCurGhostLoc(g) == node && game.getCurGhostDir(g) != dir)
				return true;
		return false;
	}
	
	/*
	 * Returns the id of the highest scoring node
	 */
	private int bestNode(float[] scores) {
		int best = -1;
		for (int i=0; i<scores.length; i++)
			if (scores[i] >= 0 && (best == -1 || scores[i] > scores[best]) && i != game.getCurPacManLoc())
				best = i;

		return best;
	}
	
	/*
	 * Travel the maze looking for the next node that is nearer to the destination node.
	 * In the cases where we have more than one "shortest" route, the one with the most point is taken.
	 */
	private void travel(int[] travelled, float [] scores, float [] pathScores, int to, int node, int dist, float score, ArrayList<Integer> path) {
		if (scores[node] < 0 || dist > 500 || (travelled[node] != -1 && (dist > travelled[node] || (dist == travelled[node] && pathScores[node] > score))))
			return;

		travelled[node] = dist;
		pathScores[node] = score;
		int ix = path.size();
		path.add(ix, node);
		if (node != to) {
			//Continue on paths nearer to the destination
			for (int d=0; d<4; d++) {
				int next = game.getNeighbour(node, d);
				if (next != -1)
					travel(travelled, scores, pathScores, to, next, dist+1, score+scores[next], path);
			}
		} else {
			bestPath = new int[path.size()];
			for (int i=0; i<path.size(); i++)
				bestPath[i] = path.get(i);
		}
		path.remove(ix);
	}
	
	/*
	 * Returns the direction to head safely to the given node
	 */
	private int bestDir(int to, float[] scores) {
		if (to == -1)
			return -1;
		
		//Walk the safe nodes (score >= 0) and find the path with the shortest distance and highest score
		int[] travelled = new int[game.getNumberOfNodes()];
		float[] pathScore = new float[game.getNumberOfNodes()]; //Total score of all nodes on path
		for (int i=0; i<pathScore.length; i++) {
			pathScore[i] = -1;
			travelled[i] = -1;
		}
		bestPath = null;
		travel(travelled, scores, pathScore, to, game.getCurPacManLoc(), 0, scores[game.getCurPacManLoc()], new ArrayList<Integer>());
		if (bestPath != null && bestPath.length > 1)
			for (int d=0; d<4; d++)
				if (game.getNeighbour(bestPath[0], d) == bestPath[1])
					return d;
		System.out.printf("Failed to find direction from %d (%d, %d) to %d (%d, %d)\n",
				game.getCurPacManLoc(),game.getX(game.getCurPacManLoc()), game.getY(game.getCurPacManLoc()), to, game.getX(to), game.getY(to));
		return -1;
	}
	
	@Override
	public String getGroupName() {
		return "test2";
	}
}